//
// Created by Martin on 2021/10/27.
//

#include <iostream>
#include <deque>
#include <stdio.h>
#include <map>

#define N_MAX  150000
#define Q_MAX  400000

using namespace std;

map<int, deque<int>> d;

void read(int &x)
{
    char ch = getchar();
    x = 0;
    for (; ch < '0' || ch > '9'; ch = getchar());
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
}

int main()
{
    int n, q;
    while (scanf("%d%d", &n, &q) != EOF)
    {
        if (n < 1 || n > N_MAX)
        {
            printf("invalid N = %d\n", n);
            exit(-1);
        }
        if (q < 1 || q > Q_MAX)
        {
            printf("invalid Q = %d\n", q);
            exit(-1);
        }

        for (int i = 1; i <= n; ++i) {
            d[i].clear();
        }

        int k, u, v, w, val;
        while (q-- > 0)
        {
            read(k);
            switch (k) {
                case 1:
                    read(u);
                    read(w);
                    read(val);
                    if (u < 1 || u > n) {
                        printf("invalid u = %d\n", u);
                        continue;
                    }

                    if (w == 0)
                        d[u].push_front(val);
                    else
                        d[u].push_back(val);
                    break;

                case 2:
                    read(u);
                    read(w);
                    if (u < 1 || u > n) {
                        printf("invalid u = %d\n", u);
                        continue;
                    }

                    if (d[u].empty()) printf("-1\n");
                    else
                    {
                        if (w == 0)
                        {
                            printf("%d\n", d[u].front());
                            d[u].pop_front();
                        }
                        else
                        {
                            printf("%d\n", d[u].back());
                            d[u].pop_back();
                        }
                    }
                    break;

                case 3:
                    read(u);
                    read(v);
                    read(w);
                    if (u < 1 || u > n) {
                        printf("invalid u = %d\n", u);
                        continue;
                    }
                    if (v < 1 || v > n) {
                        printf("invalid v = %d\n", v);
                        continue;
                    }

                    if (w == 0)
                    {
                        d[u].insert(d[u].end(), d[v].begin(), d[v].end());
                    }
                    else
                    {
                        d[u].insert(d[u].end(), d[v].rbegin(), d[v].rend());
                    }

                    d[v].clear();
                    break;
            }
        }
    }
    return 0;
}